/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 *
 *@author : sunzb(sunzb@hsit.com.cn)
 *@date: 2019/5/13
 */
// easy
public class _1_20_ValidParentheses {

    // 2 ms	33.3 MB 效率优
    public static boolean isValid(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for (int i = 0; i < len; i++) {
            Character key = chars[i];
            if (map.containsKey(key)) {
                Character pop = null;
                try {
                    pop = stack.pop();
                } catch (Exception ex) {
                    return false;
                }
                if (map.get(key) != pop) {
                    return false;
                }
            } else {
                stack.push(chars[i]);
            }
        }
        return stack.isEmpty();
    }

    // 82 ms	36.7 MB,效率太差
    public static boolean isValid2(String s) {
        int len;
        do {
            len = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (len != s.length());
        return len == 0;
    }

    public static void main(String[] args) {
        System.out.println(isValid("()"));
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("(]"));
        System.out.println(isValid("([)]"));
        System.out.println(isValid("{[]}"));
    }
}
